﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ActivitySelector
{
    public class ActivitySelector
    {
        /*
         * Singleton
         */
        public static ActivitySelector Instance
        {
            get
            {
                if (_instance == null)
                {
                    _instance = new ActivitySelector();
                }
                return _instance;
            }
           
        }
        public bool LastToStart = false;
        public int interations = 1;

        /*
         * General List being used by the application
         */
        public List<Activity> AllActivities
        {
            get { return _allActivities; }
        }

        public void add(int startTime, int finishTime)
        {
            Activity _new = new Activity(startTime, finishTime);
            _allActivities.Add(_new);
            Console.WriteLine("New Activity Added: Start Time: " + startTime + " Finish Time: " + finishTime);
        }

        private List<Activity> _allActivities = new List<Activity>();
        private static ActivitySelector _instance;
    }
    public class LastToStartActivityComparer : IComparer<Activity>
    {
        int IComparer<Activity>.Compare(Activity obj1, Activity obj2)
        {
          
            if (obj1.StartTime < obj2.StartTime)
                return 1;
            if (obj1.StartTime == obj2.StartTime)
                return 0;
            else
                return -1;
        }
    }
    public class LeastDurationActivityComparer : IComparer<Activity>
    {
        int IComparer<Activity>.Compare(Activity obj1, Activity obj2)
        {

            if (obj1.StartTime - obj1.FinishTime < obj2.StartTime - obj2.FinishTime)
                return 1;
            if (obj1.StartTime - obj1.FinishTime == obj2.StartTime - obj2.FinishTime)
                return 0;
            else
                return -1;
        }
    }

    public class EarliestStartComparer : IComparer<Activity>
    {
        int IComparer<Activity>.Compare(Activity obj1, Activity obj2)
        {

            if (obj1.StartTime  > obj2.StartTime)
                return 1;
            if (obj1.StartTime == obj2.StartTime )
                return 0;
            else
                return -1;
        }
    }
    public class MostCompatible : IComparer<Activity>//orders by the most compatible objects being lowest in the index.
    {
        public List<Activity> Against = null;
        int IComparer<Activity>.Compare(Activity obj1, Activity obj2)
        {
            if (Against == null)
                return 0;
            int val1 = 0;
            int val2 = 0;
            foreach (Activity a in Against)
            {
                if(obj1.isCompatible(a))
                    val1++;
                if (obj2.isCompatible(a))
                    val2++;
            }
            if (val1 > val2)
                return -1;
            if (val1 == val2)
                return 0;
            else
                return 1;
        }
    }
    public class Activity : IComparable
    {
        public Activity()
        {
        }
        public Activity(int s, int f)
        {
            StartTime = s;
            FinishTime = f;
        }

        public override string ToString()
        {
            string indexSpace = "";
            string startSpace = "";
            string finishSpace = "";
            if (index < 10)
                indexSpace = "  ";
            if (StartTime < 10)
                startSpace = "  ";
            if (FinishTime < 10)
                finishSpace = "  ";
            return "A" + index + indexSpace + ": s" + StartTime + startSpace + ", f" + FinishTime + finishSpace;
        }
        public int index = 0;
        public int StartTime = 0;
        public int FinishTime = 0;

        public int CompareTo(object obj)
        {
            Activity obj2 = obj as Activity;
            if (obj2.FinishTime > FinishTime)
                return -1;// sorting lowest to highest, values are reveresed.
            else if (obj2.FinishTime == FinishTime)
                return 0;
            else return 1;
        }

       
        public bool isCompatible(Activity a)
        {
            if (a.StartTime > FinishTime || a.FinishTime < StartTime)
                return true;
            return false;
        }
 
    }
    public class ActivitySelectorReccuranceFunctions
    {
        public static List<Activity> MostCompatbileActivitiesSelector(List<Activity> activities)
        {
            List<Activity> retList = new List<Activity>();
            Activity[] usingList = new Activity[activities.Count];
            List<Activity> comparingList = new List<Activity>();
            activities.CopyTo(usingList);
            foreach (Activity a in usingList)
            {
                comparingList.Add(a);
            }
            MostCompatible mc = new MostCompatible();
            mc.Against = ActivitySelector.Instance.AllActivities;
            for (int i = 0; i < comparingList.Count; i++)
            {
                bool compatible = true;
                foreach (Activity a in retList)
                {
                    if (!a.isCompatible(activities[i]))
                    {
                        compatible = false;
                        break;
                    }
                }
                if (compatible)
                {
                    retList.Add(comparingList[i]);
                    comparingList.Remove(comparingList[i]);
                    mc.Against = comparingList;
                    comparingList.Sort(mc);//resort for given 
                    i = 0;//go through starting at zero again.
                }
            }
            retList.Sort(new EarliestStartComparer());
            return retList;
        }
        public static List<Activity> CheckAgainstAllIn(List<Activity> activities)
        {
            List<Activity> retList = new List<Activity>();
            
            for (int i = 0; i < activities.Count; i++)
            {
                bool compatible = true;
                foreach (Activity a in retList)
                {
                    if (!a.isCompatible(activities[i]))
                    {
                        compatible = false;
                        break;
                    }
                }
                if (compatible)
                    retList.Add(activities[i]);
            }
            return retList;
        }
        public static List<Activity> GreedyActivitySelector(List<Activity> activities, Activity include)
        {
            if (activities.Count < 1)
                return new List<Activity>();
            List<Activity> retList = new List<Activity>();
            activities.Remove(include);
            
            int first = 0;
            while (first < activities.Count)
            {
                if (!activities[first++].isCompatible(include))
                    continue;
                retList.Add(activities[--first]);
                break;
            }
            if (retList.Count < 1)
            {
                retList.Add(include);
                return retList;//trivial solution 1
            }

            

            for (int j = first +1; j < activities.Count; j++)
            {
                if (retList[retList.Count - 1].isCompatible(activities[j]) && activities[j].isCompatible(include))
                {
                        retList.Add(activities[j]);
                   
                }
            }
            retList.Add(include);
            retList.Sort();
            activities.Add(include);
            activities.Sort();
            if (ActivitySelector.Instance.LastToStart)
                retList.Reverse();
            return retList;
        }
        public static List<Activity> GreedyActivitySelector(List<Activity> activities)
        {
            if (activities.Count < 1)
                return new List<Activity>();
            List<Activity> retList = new List<Activity>();

            
            retList.Add(activities[0]);
          

            for (int j = 1; j < activities.Count; j++)
            {
                if (retList[retList.Count - 1].isCompatible(activities[j]))
                {
                    retList.Add(activities[j]);
                }
            }
            if (ActivitySelector.Instance.LastToStart)
                retList.Reverse();
            return retList;
        }
         /**
         * base call for solving recursively with an included activity
         */
        public static List<Activity> RecursiveActivitySelector(List<Activity> activities, Activity include)
        {
            if (activities.Count < 1)
                return new List<Activity>();

            
            activities.Remove(include);
            List<Activity> retList = RecursiveActivitySelector(activities, 0, activities.Count, include);

            retList.Add(include);
            activities.Add(include);

            if (!ActivitySelector.Instance.LastToStart)
            {
                activities.Sort();
                retList.Sort();
            }
            else
            {
                activities.Sort(new LastToStartActivityComparer());
                retList.Sort(new LastToStartActivityComparer());
                foreach (Activity a in retList)
                {
                    if (a.index == 0)
                    {
                        retList.Remove(a);
                        break;
                    }
                }

                retList.Reverse();
            }
            return retList;
        }
        /**
       * base call for solving recursively
       */
        public static List<Activity> RecursiveActivitySelector(List<Activity> activities)
        {
            if (activities.Count < 1)
                return new List<Activity>();

            List<Activity> retList = RecursiveActivitySelector(activities, 0, activities.Count);
            foreach (Activity a in retList)
            {
                if (a.index == 0)
                {
                    retList.Remove(a);
                    break;
                }
            }
            if (ActivitySelector.Instance.LastToStart)
                retList.Reverse();
            return retList;
        }
        /**
         * The Recursive overload for an included activity
         */
        public static List<Activity> RecursiveActivitySelector(List<Activity> activities, int k, int n, Activity include)
        {
            int m = k + 1;

            while (m < n && !(activities[k].isCompatible(activities[m]) && activities[m].isCompatible(include)) )
                m++;

            if (m < n)
            {
                List<Activity> retList = RecursiveActivitySelector(activities, m, n, include);
                retList.Insert(0, activities[m]);
                return retList;
            }

            return new List<Activity>();
        }
        /**
         * The Recursive overload for no special included activity
         */
        public static List<Activity> RecursiveActivitySelector(List<Activity> activities, int k, int n)
        {
            int m = k + 1;

            while ( m  < n && !activities[k].isCompatible(activities[m]))
                m++;

            if (m < n)
            {
                List<Activity> retList = RecursiveActivitySelector(activities, m, n);
                retList.Insert(0,activities[m]);
                return retList;
            }

            return new List<Activity>();
        }
        
    }
}
